package com.sjf.day04.dynamic;

import java.util.Arrays;

/**
 * 背包问题
 *
 * @author <huangtang>
 * @since 2022/1/18 10:14
 **/
public class KnapsackProblem {

    public static void main ( String[] args ) {
        int[] w = { 1 , 4 , 3 };//物品的重量
        int[] val = { 1500 , 3000 , 2000 }; //物品的价值
        int m = 4; //背包的容量
        int n = val.length; //物品的个数

        //v[i][j]表示在前i个物品种能够装入最大容量为j的背包中的最大价值
        int[][] v = new int[n + 1][m + 1];
        //记录放入商品的情况
        int[][] path = new int[n + 1][m + 1];
        //初始化第一行和第一列,可以忽略

        //动态规划处理
        for ( int i = 1 ; i < v.length ; i++ ) { //不处理第一列
            for ( int j = 1 ; j < v[0].length ; j++ ) { //不处理第一行
                if ( w[i - 1] > j ) {
                    v[i][j] = v[i - 1][j];
                } else {
                    //v[ i ][ j ] = Math.max ( v[ i - 1 ][ j ] , val[ i - 1 ] + v[ i - 1 ][ j - w[ i - 1 ] ] );
                    //为了记录商品存放到背包的情况
                    if ( v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]] ) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        //把当前的情况记录到path
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }

        for ( int[] ints : v ) {
            System.out.println (Arrays.toString (ints));
        }

        System.out.println ("放入的商品情况");
        for ( int[] ints : path ) {
            System.out.println (Arrays.toString (ints));
        }
    }
}
